/**
 *  二叉树的高度 - 广度优先遍历
 */
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr){};
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){};
    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x), left(left), right(right){};
    void setVal(int x) { val = x; }
    void setAttribute(int x, TreeNode* l, TreeNode* r) {
        val = x;
        left = l;
        right = r;
    }
    void setChildren(TreeNode* l, TreeNode* r) {
        left = l;
        right = r;
    }
};

/**
 * 获取二叉树高度 - 广度优先遍历
 */
int getDepth(TreeNode* tree) {
    queue<TreeNode*> queue;
    int num;
    int depth = 0;

    if (tree == nullptr) {
        return 0;
    }
    queue.push(tree);
    while (!queue.empty()) {
        depth++;
        num = queue.size();
        for (int i = 0; i < num; i++) {
            TreeNode* node = queue.front();
            queue.pop();
            if (node->left != nullptr) {
                queue.push(node->left);
            }
            if (node->right != nullptr) {
                queue.push(node->right);
            }
        }
    }

    return depth;
}

void test() {
    // 1. 构造一棵树。
    TreeNode* t1 = new TreeNode(1);
    TreeNode* t2 = new TreeNode(2);
    TreeNode* t3 = new TreeNode(3);
    TreeNode* t4 = new TreeNode(4);
    TreeNode* t5 = new TreeNode(5);
    TreeNode* t6 = new TreeNode(6);

    t1->setChildren(t2, t3);
    t2->setChildren(t4, t5);
    t5->setChildren(t6, nullptr);

    cout << "二叉树的高度为: " << getDepth(t1) << endl;
}

int main() {
    test();
    return 0;
}